|
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether a given number belongs to the set. A more general class of sets consists of the recursively enumerable sets, also called semidecidable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number ''is'' in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set. A set which is not computable is called noncomputable or undecidable. ==Formal definition== A subset of the natural numbers is called recursive if there exists a total computable function such that if and if . In other words, the set is recursive if and only if the indicator function is computable. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「recursive set」の詳細全文を読む スポンサード リンク
|